Comment Feed for Best way to implement these CRUD-(like) operations (TechOff on Channel 9)

Re: Re: Best way to implement these CRUD-(like) operations

Bass — Wed, 24 Jun 2009 02:44:44 GMT

Doesn't seem possible since R can be any number. :\

Re: Best way to implement these CRUD-(like) operations

Joe Chung — Wed, 24 Jun 2009 02:11:17 GMT

How about a bloom filter?

Re: Best way to implement these CRUD-(like) operations

Bass — Tue, 23 Jun 2009 23:55:31 GMT

moved to new post

Re: Re: Re: Re: Re: Re: Best way to implement these CRUD-(like) operations

Bass — Tue, 23 Jun 2009 23:28:34 GMT

Let M be a set vectors, of dimension N (where N > 100); Let G be a vector in M. Now find all vectors in M that less then distance R from G.

Can this problem be solved without linearly accessing every vector in M?

Re: Re: Re: Re: Re: Best way to implement these CRUD-(like) operations

DCMonkey — Tue, 23 Jun 2009 22:57:06 GMT

Some more general info might still be helpful. Will the set of data involved in the search calculation fit in memory? Is there any pattern to the data that can be taken advantage of? Is some kind of preprocessing step allowed with a lengthly runtime or do the searches need to be fast on fresh raw data? How much hardware can you throw at the problem? Is there an opportunity for parallelization? Is this why you are interested in Hadoop (from that other thread)?

Also, by "fast" do you mean seconds, minutes, hours, or days?

Re: Re: Re: Re: Best way to implement these CRUD-(like) operations

Bass — Tue, 23 Jun 2009 22:27:23 GMT

I can't really tell, it's all under NDA. Sorry. :(

Re: Re: Re: Best way to implement these CRUD-(like) operations

Matthew van Eerde — Mon, 22 Jun 2009 22:46:03 GMT

I'm a little lost now. You're looking to apply a distance metric over many dimensions? RMS of the distances across each dimension is the usual answer, but I am getting very curious as to what kind of domain you're working on.

Re: Re: Re: Best way to implement these CRUD-(like) operations

W3bbo — Mon, 22 Jun 2009 21:13:34 GMT

There's a set of hash functions that return similar values for similar inputs. One example is a blur filter; I forget the set's name though.

For thousands of dimensions.... just what kind of data are you processing?

Re: Re: Re: Best way to implement these CRUD-(like) operations

Bass — Mon, 22 Jun 2009 20:23:19 GMT

I'm talking about thousands of dimensions, there are tricks for low dimensional spacial data, but they kind of become crap at higher dimensions. Every RDBMS I've looked at can only handle 4 dimensions at most.

Re: Re: Best way to implement these CRUD-(like) operations

Bass — Mon, 22 Jun 2009 20:21:20 GMT

No a hash would be completely useless, unless you can figure out how to do a distance calculation on a hash. :)

Re: Re: Best way to implement these CRUD-(like) operations

W3bbo — Mon, 22 Jun 2009 01:02:10 GMT

What about creating an index for each dimension, then you can do linear-or-better search on the indexes for each dimension to get the desired result; this also allows for finding points in space within a specified radii of the search point too. I assume you could get your RDBMS to maintain the indexes for you.

Unless I'm missing something?

Re: Best way to implement these CRUD-(like) operations

Matthew van Eerde — Sun, 21 Jun 2009 23:15:44 GMT

Second the hash suggestion.

Re: Re: Re: Re: Best way to implement these CRUD-(like) operations

Herbie Smith — Sun, 21 Jun 2009 20:40:22 GMT

Right, OK, so not really your basic CRUD then. ;)

The way I think of balanced tree is that it's optimised to compartmentalise data through one dimension, but you need to comparmentionalise data through N-dimensions. So you need a way to group the data into blocks where each block represents a partition of the n-dimensional space, but in such a way that you can quickly tell if a specific point is greater than or less than each of the n-dimension partitions of that block so you can 'zoom in' to the correct place easily.

Yeah. Good luck with that :D

So are you looking for a specific piece of data with a specific co-ordinate (like you know specifically that there is a piece of data for [1, 2, 3]? If so, could you create a hash for the specific co-ordinate and use a hashtable for storage and retrieval.

Or are you more like looking for all the data within a bounded range\area? That's not going to be easy.

Let us know how you get on.

Herbie

Re: Re: Re: Best way to implement these CRUD-(like) operations

Bass — Sun, 21 Jun 2009 19:36:24 GMT

I'm looking for a data struture to efficient search through spatial data of very high dimensionality. This is not a trivial question apperently (looks to be an area of active research). AFAIK there is no easy non-linear struture like a BST can accomplish this.

Re: Re: Best way to implement these CRUD-(like) operations

Herbie Smith — Sun, 21 Jun 2009 19:13:50 GMT

Why would you need to iterate for CRUD operations? I thought a dictionary the keyed lookup was faster than iterating through an array (there may be a case where small arrays are faster, but you'd have to perf analyse that).

The .NET dictionary allows access to the Keys and values as separate lists should you need them.

Of course the real solution is to create a generic interface to your system and perf test with different data structures :) Borland's BIDS library was a great example where the underlying data structure (array, linked list, doubly linked list) was changeable for each algorithmic data type (queue, stack, etc), allowing you to test the performace of different implementations.

Herbie

EDIT: Additionally, you might want to look up how relational databases handle these types of things: probably a balanced tree implementation would be a good place to start for fast searches.

Re: Best way to implement these CRUD-(like) operations

Bass — Sun, 21 Jun 2009 16:19:53 GMT

Isn't Dictionary slow for iteration compared to an Array or a List?

Re: Best way to implement these CRUD-(like) operations

Scott — Sat, 20 Jun 2009 16:36:46 GMT

Without knowing the context it's a little hard to give advice, but if you want to search items using a key, I'd use a Dictionary object to store my items.