Databases
StackOverflow2013
Postsdbo
POIdea for a data structure to store 2D data?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIdea for a data structure to store 2D data?
    primarykey
    data
    text
    <p>I have a large 2D grid, x-by-y. The user of the application will add data about specific points on this grid. Unfortunately, the grid is far too big to be implemented as a large x-by-y array because the system on which this is running does not have enough memory.</p> <p>What is a good way to implement this so that only the points that have data added to them are stored in memory?</p> <p>My first idea was to create a BST of the data points. A hash function such as "(long)x&lt;&lt;32 + y" would be used to compare the nodes.</p> <p>I then concluded that this could lose efficiency if not well balanced so I came up with the idea of having a BST of comparable BSTs of points. The outer BST would compare the inner BSTs based on their x values. The inner BSTs would compare the points by their y values (and they would all have the same x). So when the programmer wants to see if there is a point at (5,6), they would query the outer BST for 5. If an inner BST exists at that point then the programmer would query the inner BST for 6. The result would be returned.</p> <p>Can you think of any better way of implementing this?</p> <p>Edit: In regards to HashMaps: Most HashMaps require having an array for the lookup. One would say "data[hash(Point)] = Point();" to set a point and then find the Point by hashing it to find the index. The problem, however, is that the array would have to be the size of the range of the hash function. If this range is less than the total number of data points that are added then they would either have no room or have to be added to an overflow. Because I don't know the number of points that will be added, I would have to make an assumption that this number would be less than a certain amount and then set the array to that size. Again, this instantiates a very large array (although smaller than originally if the assumption is that there will be less data points than x*y). I would like the structure to scale linearly with the amount of data and not take up a large amount when empty.</p> <p>It looks like what I want is a SparseArray, as some have mentioned. Are they implemented similarly to having a BST inside of a BST?</p> <p>Edit2: Map&lt;> is an interface. If I were to use a Map then it looks like TreeMap&lt;> would be the best bet. So I would end up with TreeMap&lt; TreeMap&lt; Point> >, similar to the Map&lt; Map&lt; Point> > suggestions that people have made, which is basically a BST inside of a BST. Thanks for the info, though, because I didn't know that the TreeMap&lt;> was basically the Java SDK of a BST.</p> <p>Edit3: For those whom it may concern, the selected answer is the best method. Firstly, one must create a Point class that contains (x,y) and implements comparable. The Point could potentially be compared by something like (((long)x)&lt;&lt;32)+y). Then one would TreeMap each point to the data. Searching this is efficient because it is in a balanced tree so log(n) cost. The user can also query all of this data, or iterate through it, by using the TreeMap.entrySet() function, which returns a set of Points along with the data.</p> <p>In conclusion, this allows for the space-efficient and search-efficient implementation of a sparse array, or in my case, a 2D array, that can also be iterated through efficiently.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USReed B
    1. USReed B
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIdea for a data structure to store 2D data?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIdea for a data structure to store 2D data?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIdea for a data structure to store 2D data?
      1. This table or related slice is empty.
      1. VTUpMod
    1. COhttp://stackoverflow.com/questions/390181/sparse-matrices-arrays-in-java
      singulars
      1. POIdea for a data structure to store 2D data?
      1. USGriffeyDog
    2. COdont reinvent the wheel, look at spatial data structures
      singulars
      1. POIdea for a data structure to store 2D data?
      1. USAlexWien
    3. COYou seem to be interested more in the underlying implementation of the data structure, instead of how you're going to use it. If you need some spacial queries (points with x between 10 and 40), or nearest neighbor queries, you could use some of the structures AlexWien mentioned, or some navigable map. If you need to look-up some specific point only, a plain old HashMap would do a good job - http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
      singulars
      1. POIdea for a data structure to store 2D data?
      1. USjmruc
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload