home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / database / 6528 < prev    next >
Encoding:
Text File  |  1992-09-03  |  4.0 KB  |  101 lines
  1. Newsgroups: comp.databases
  2. From: gtoal@pizzabox.demon.co.uk (Graham Toal)
  3. Path: sparky!uunet!pipex!demon!pizzabox.demon.co.uk!gtoal
  4. Subject: SUMMARY: Re: free text indexing algorithm refs wanted...
  5. Distribution: world
  6. Organization: Cuddlehogs Anonymous
  7. Lines: 89
  8. Date: Thu, 3 Sep 1992 01:18:18 +0000
  9. Message-ID: <715483098snx@pizzabox.demon.co.uk>
  10. Sender: usenet@gate.demon.co.uk
  11.  
  12. I wrote:
  13.  
  14. >Having implemented a database using a really cool set of algorithms
  15. >and data structures, which let us do just about anything, we find it's
  16. >depressingly slow compared to some commercial systems.  We've have
  17. >worked out what they must be doing by treating them as a black box
  18. >and throwing queries at them, and working out the complexity of the
  19. >search algorithms they must be using.  Any pointers to papers or
  20. >articles on different data structures for free text systems?
  21.  
  22.  
  23. Thanks to all of you who answered.  I'll follow up the references
  24. suggested, and write some more on what we're doing later.  A quick
  25. comment though is that the time for turning a key into a pointer
  26. to a list of occurances of that word *isn't* the bottleneck; the
  27. problems we have are more to do with efficient operations on these
  28. lists - including AND and OR, but also more powerful ones.  We have
  29. hierarchical SGML structured documents, so simple solutions like
  30. separate indices for each field don't work.
  31.  
  32. Our structure simply has a 32-bit pointer to the word; other people
  33. may include various bits of info too.  (Liam Quinn - we chatted about
  34. this a long time ago when we first started this project.  Your scheme
  35. is the sort of thing I was looking for info on, though I'm particularly
  36. wondering about real live systems that perform well on CDs at slow CD
  37. speeds - there's probably only commercial ones like this...)
  38.  
  39. My apologies to the people who mailed me for not replying individually;
  40. I've fire-fighting at work at the moment and can't keep up.  I've filed
  41. all your mail and will reply personally as soon as things lighten up.
  42.  
  43. [Ed Fox - I won't be in Cambridge, but will you be passing through
  44. London at all?]
  45.  
  46. ========
  47.  
  48. From: "Sanjiv K. Bhatia" <sanjiv@redbird.umsl.edu>
  49.  
  50. Have you checked the standard books on Information Retrieval like the classic
  51. text by van Rijsbergen and another book by Salton.  I can send you the complete
  52. reference if you desire.
  53.  
  54. It may also help to check the implemented schemes in the SMART retrieval
  55. environment available from Cornell University for a small fee.  And there is
  56. the overly stupid indxbib in Unix but it comes for free.
  57.  
  58. ========
  59.  
  60. From: David Grossman <grossman@eola.cs.ucf.edu>
  61.  
  62. Do you have a copy of Mark Zimmerman's free text browser. Its
  63. shareware and comes with source code. I can mail it to you if
  64. you'd like, he's got some comments that might help. As for IR
  65. design there are probably some articles that might interest you
  66. in any of the last couple SIGIR (Special interest group on 
  67. information retrieval).
  68.  
  69. ========
  70.  
  71. From: QiFan Chen <chenq@hal.com>
  72.  
  73. I noticed that you have posted a message "free text indexing algorithm
  74. refs wanted..." on the comp.databases. It is interesting
  75. as my colleagues and I also work on SGML database related issues 
  76. and like to share expereience with each other on this subject.
  77.  
  78. Back in school, my professors and I have jointly designed a set 
  79. of hash algorithms such that given a key, the record it 
  80. associated with can be read in with one disk access.  The 
  81. hash function maintains 1-to-1 mapping from key to record. 
  82. So there is no collision and the exact record address can be 
  83. computed from the key. We call these functions minimal 
  84. perfect hash functions. The material is covered in the first 
  85. issue of CACM of this year. You can contact 
  86.  
  87. Dr. Edward A. Fox
  88. Dept. of Computer Science 
  89. Va Tech
  90. Blacksburg, Va 24061
  91.  
  92. email: fox@fox.cs.vt.edu
  93. ph: 703-231 5113
  94.  
  95. for more information on those algorithms. These algorithms 
  96. should be very useful to speed your database access up.
  97.  
  98. Also in Hal, we are using object-oriented database tech. to
  99. store SGML data. It is our experience that the data should be
  100. carefully re-origanized to allow good performance.
  101.