Re: [bdbxml] Regular expressions in bdbxml

On Aug 18, 2005, at 12:24 PM, Dan Brian wrote:

>>> It's impossible for any regular expression index to provide  
>>> lookup speed close to the current index types. All they can do is  
>>> dramatically lessen the set size for which the regular expression  
>>> must be executed against each record. And even then, it's usually  
>>> just for POSIX 1003.2 regexes, as opposed to PCRE, and  
>>> implementing "multigram" indexes is not a small job.
>>>
>>> But, yes, this would be a nice feature. :-)
>>>
>>>
>>
>> Right, but that's what indexing is all about, reducing the set of  
>> potential matches to lower query processing time.  Here's one  
>> paper we're reviewing that has an interesting approach.
>>
>> http://oak.cs.ucla.edu/~cho/papers/cho-regex.pdf
>>
>
> Yeah, the Cho solution uses multigram indexes. I only meant to say  
> that these indexes often don't yield the improvement that might be  
> expected, and often (not always) there are better ways to do  
> queries (especially in XQuery, where you can do your own set  
> processing). This depends in large part on the regex itself, of  
> course.

Right, good point.  People are going to use regex and expect better  
than O(n) speed so this is a must have feature for us at some point.   
Seems like we should put it on the list sooner than later.  The Cho  
solution is just one way to reduce the set, as you point out, and  
some hybrid of solutions might be best.  We've not really made up our  
minds just yet.

> And yes, I think this would be an awesome addition to BDB XML. In  
> truth, this would be a great use of BDB itself: a general-purpose  
> regular expression indexer. Lots of applications outside of BDB XML.

Send me email about what you mean by "BDB and regex", I'd like to  
hear more.

-greg

> Regards,
> Dan



------------------------------------------
To remove yourself from this list, send an
email to [email protected]