need to solve incremental hash problem

[dankin]

I have a linked list of data objects.  Each data object contains a word or short phrase associated with it.  As each node is added to the linked list, I'd like to build an incremental hash for that node.  So, I woud like to take the hash from the previous node and incrementaly add to the hash to include the current node's phrase.  The end result of this is that I'd like to be able to search the list using words in any order which would then point me to the node at the end of the list which contained the words.  There would be multiple lists extending from the top link.

 

Is it possible to use some sort of incremental hash to allow search of these linked lists?

[requinix]

As I understand them, that's not quite what incremental hashes are for.

 

It sounds like there's some information you're holding back. How many lists and data objects are you holding in memory? What's the significance of these lists? Are the words/phrases unique?

[dankin]

Thanks for your reply.  Sorry, I was traveling yesterday and didn't see it.

 

Each of these objects would be contained in a mysql data base.  There would be a single object at the top of all the lists, and each object would have multiple objects linked to it and stretching out below it.  So, there could be a very, very,  large number of these objects in the data base.

 

Words or phrases in a particular linked list would not be be unique to other nodes in the data base.  The only thing that makes them unique is the sequence of word or phrases coming before and after them.

 

If I wanted to find a particular node in the data base, I'd like to search for it using its word/phrase along with some words/phrases from other nodes which happen to be in the same linked list.

 

I was thinking that I might be able to build a hash using the first word and store it on the node.  Then, as the second node is linked, the previous hash could be agumented using the new nodes word/phrase and then this augmented hash would be stored in the second node.  I'm hoping to find a method that would allow searching of the data base using some of these word/phrases and being led to a linked list which contains nodes that have these words/phrases. 

 

Any ideas on how to do something like that?

[requinix]

As I said, incremental hashes don't do that. That's not what they're for nor how they work.

 

I think you're overcomplicating the issue. Build a set of lists that contain the first word. Then, for each subsequent word, filter the set down by removing lists that don't contain each word. For instance,

SELECT * FROM wordlists WHERE id IN (
SELECT listid FROM wordlists_words WHERE word = "fox" AND listid IN (
	SELECT listid FROM wordlists_words WHERE word = "brown" AND listid IN (
		SELECT listid FROM wordlists_words WHERE word = "quick" AND listid IN (
			SELECT listid FROM wordlists_words WHERE word = "the"
		)
	)
)
)

[xyph]

Store your linked lists in a table. If you can only have a set length for your lists, say, 10 words, have a column for each possible word or phrase. If you want to select every list with word number 10 (I'm assuming your words/phrases have an id) you could:

 

SELECT * FROM `lists` WHERE `c1` = 10 OR `c2` = 10 OR `c3` = etc.

 

If your list could be any length long, perhaps store your values as text, with a leading and training pipe, and pipes in between. Say your list had words 2,6,24,17 - you'd store it like |2|6|24|17| Your query would then look like

 

SELECT * FROM `lists` WHERE `words` LIKE '%|24|%'

[requinix]

If your list could be any length long, perhaps store your values as text, with a leading and training pipe, and pipes in between. Say your list had words 2,6,24,17 - you'd store it like |2|6|24|17| Your query would then look like

 

SELECT * FROM `lists` WHERE `words` LIKE '%|24|%'

Have to disagree with that. I have never seen a situation where storing delimited data is even remotely appropriate, and this isn't one.

[xyph]

Was trying to keep it simple. If efficiency is more important than simplicity, the alternate solution is

 

Make two tables, one to store lists, the other to store items in a given list.

 

SELECT `parentList` FROM `listEntries` WHERE `word` = 10 GROUP BY `parentList`

 

Should give you a result of lists with any given word(s).