3 ms·

96% of change is append. 0.0001% would be delete. Sorts of views might be: "show me objects that have lat xx and long yy but tagged "buttons" and created on mm

by imajes 17y ago

96% of change is append. 0.0001% would be delete. Sorts of views might be: "show me objects that have lat xx and long yy but tagged "buttons" and created on mm/dd/yyyy" in the basic instance, but also "show me objects that my friends like" as a more complex example. Makes me think that what I really need is a graph db- object relationship seems the key factor.

ars 17y ago
So you do have updates? Because updates makes a database more complicated. If you need lat/lng then you need an R-tree and very few databases come with that. Sounds to me like your going to have to write your own database - or more accurately your own index. Basically store data as append only, and handle change as delete/append. Store just the offset to the data as the key. I really hope your index can fit on one machine. Do it like the facebook link I gave you earlier. Your going to have a hard time with index merges (lat/lng merge with tags). Maybe a better idea is don't store the object in the database, but just the offset to it (plus machine ID). Then use any commercial database that has an R-Tree. You have 200GB to 1PT of data to store. Which needs at least 25 machines. But if you can store just the index, but not the data, maybe you can store the index on just one machine - that will makes things easier. (Obviously you'll have multiple machines with the same index for load balancing.) This might help also: http://www.ddj.com/184410998 http://www.ddj.com/184410998 (instead of an R-Tree, you might be able to a regular index).
- imajes 17y ago
  Yeah, i think there's a lot of validity in this comment... I fully expect to do stuff like abstract storage of lat/long to separate stores- so most append is really just creating a new related object- but how to store it is the fun problem :) good tips. thanks. :)
- fhars 17y ago
  PostgreSQL has spatial indexing capability, too. So you can do something like (the exact syntax for spatial ops escapes me right now): SELECT DISTINCT obj FROM media NATURAL JOIN mediatags WHERE (location INTERSECTS somebox) AND tag IN (SELECT tag FROM usertags WHERE user = 137) You will probably have to spend some quality time with the query planner figuring out how to set up your indexes so the common queries will be fast, but it should be possible. (EDIT: fighting with the formatting. Why is there no preview?)
- ajmm 17y ago
  Regarding space filling curves some implementations would be: 1) http://code.google.com/p/uzaygezen/ http://code.google.com/p/uzaygezen/ (Hilbert) 2) http://www.h2database.com/html/features.html#multi_dimensional http://www.h2database.com/html/features.html#multi_dimension... (Z-order) Other space transformations could be employed like the Pyramid technique or the iDistance (http://obsearch.net http://obsearch.net). Nevertheless, if the "intrinsic dimensionality" of your objects is too high then the curse of dimensionality comes into play and sequential scan might be cheaper. In such a case the Va-file, IQ-Tree or even "sketches" might be the only way to go.
kingsley_20 17y ago
apparently, you can aggregate lat-long into a geohash http://en.wikipedia.org/wiki/Geohash http://en.wikipedia.org/wiki/Geohash. seems like a good idea, although i havent actually tried it.

by imajes 17y ago

ars 17y ago

So you do have updates? Because updates makes a database more complicated. If you need lat/lng then you need an R-tree and very few databases come with that. Sounds to me like your going to have to write your own database - or more accurately your own index. Basically store data as append only, and handle change as delete/append. Store just the offset to the data as the key. I really hope your index can fit on one machine. Do it like the facebook link I gave you earlier. Your going to have a hard time with index merges (lat/lng merge with tags). Maybe a better idea is don't store the object in the database, but just the offset to it (plus machine ID). Then use any commercial database that has an R-Tree. You have 200GB to 1PT of data to store. Which needs at least 25 machines. But if you can store just the index, but not the data, maybe you can store the index on just one machine - that will makes things easier. (Obviously you'll have multiple machines with the same index for load balancing.) This might help also: http://www.ddj.com/184410998 http://www.ddj.com/184410998 (instead of an R-Tree, you might be able to a regular index).

imajes 17y ago
Yeah, i think there's a lot of validity in this comment... I fully expect to do stuff like abstract storage of lat/long to separate stores- so most append is really just creating a new related object- but how to store it is the fun problem :) good tips. thanks. :)
fhars 17y ago
PostgreSQL has spatial indexing capability, too. So you can do something like (the exact syntax for spatial ops escapes me right now): SELECT DISTINCT obj FROM media NATURAL JOIN mediatags WHERE (location INTERSECTS somebox) AND tag IN (SELECT tag FROM usertags WHERE user = 137) You will probably have to spend some quality time with the query planner figuring out how to set up your indexes so the common queries will be fast, but it should be possible. (EDIT: fighting with the formatting. Why is there no preview?)
ajmm 17y ago
Regarding space filling curves some implementations would be: 1) http://code.google.com/p/uzaygezen/ http://code.google.com/p/uzaygezen/ (Hilbert) 2) http://www.h2database.com/html/features.html#multi_dimensional http://www.h2database.com/html/features.html#multi_dimension... (Z-order) Other space transformations could be employed like the Pyramid technique or the iDistance (http://obsearch.net http://obsearch.net). Nevertheless, if the "intrinsic dimensionality" of your objects is too high then the curse of dimensionality comes into play and sequential scan might be cheaper. In such a case the Va-file, IQ-Tree or even "sketches" might be the only way to go.

kingsley_20 17y ago

apparently, you can aggregate lat-long into a geohash http://en.wikipedia.org/wiki/Geohash http://en.wikipedia.org/wiki/Geohash. seems like a good idea, although i havent actually tried it.