Browsing by Author "Daoud, Amjad M."

Now showing 1 - 5 of 5
  • Thumbnail Image
    Development of a Modern OPAC: From REVTOLC to MARIAN
    Fox, Edward A.; France, Robert K.; Sahle, Eskinder; Daoud, Amjad M.; Cline, Ben E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1993-02-01)
    In the Retrieval Experiment -- Virginia Tech OnLine Catalog (REVTOLC) study we carried out a large pilot test in 1987 and a larger, controlled investigation in 1990, with 216 users and roughly 500,000 MARC records. Results indicated that a forms-based interface coupled with vector and relevance feedback retrieval methods would be well received. Recent efforts developing the Multiple Access and Retrieval of Information with ANnotations (MARIAN) system have involved use of a specially developed object-oriented DBMS, construction of a client running under NeXTSTEP, programming of a distributed server with a thread assigned to each user session to increase concurrency on a small network of NeXTs, refinement of algorithms to use objects and stopping rules for greater efficiency, usability testing and iterative interface refinement.
  • Thumbnail Image
    Efficient data structures for information retrieval
    Daoud, Amjad M. (Virginia Tech, 1993-08-05)
    This dissertation deals with the application of efficient data structures and hashing algorithms to the problems of textual information storage and retrieval. We have developed static and dynamic techniques for handling large dictionaries, inverted lists, and optimizations applied to ranking algorithms. We have carried out an experiment called REVTOLC that demonstrated the efficiency and applicability of our algorithms and data structures. Also, the REVTOLC experiment revealed the effectiveness and ease of use of advanced information retrieval methods, namely extended Boolean (p-norm), vector, and vector with probabilistic feedback methods. We have developed efficient static and dynamic data structures and linear algorithms to find a class of minimal perfect hash functions for the efficient implementation of dictionaries, inverted lists, and stop lists. Further, we have developed a linear algorithm that produces order preserving minimal perfect hash functions. These data structures and algorithms enable much faster indexing of textual data and faster retrieval of best match documents using advanced information retrieval methods. Finally, we summarize our research findings and some open problems that are worth further investigation.
  • Thumbnail Image
    Order Preserving Minimal Perfect Hash Functions and Information Retrieval
    Fox, Edward A.; Chen, Qi-Fan; Daoud, Amjad M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1991)
    Rapid access to information is essential for a wide variety of retrieval systems and applications. Hashing has long been used when the fastest possible direct search is desired, but is generally not appropriate when sequential or range searches are also required. This paper describes a hashing method, developed for collections that are relatively static, that supports both direct and sequential access. The algorithms described give hash functions that are optimal in terms of time and hash table space utilization, and that preserve any a priori ordering desired. Furthermore, the resulting order preserving minimal perfect hash functions (OPMPHFs) can be found using time and space that are linear in the number of keys involved and so are close to optimal.
  • Thumbnail Image
    Performance of Some CFD Codes on the Alliant FX/8
    Abu-Sufah, Walid; Daoud, Amjad M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1988)
    Three CFD codes are ported to the Alliant FX/8. The first solves the 3-D unsteady Euler equations using an explicit finite-volume Runge-Kutta time stepping method. The second solves the same problem using the Beam and Worming implicit method. The third is ARC2D from NASA Ames which solves the unsteady 2-D Navier-Stockes equations using an implicit method. Extensive observations and results on the performance of these codes on the FX/8 are presented. Careful interaction with parallelizing compiler improves the performance some. Better results are obtained by simple recoding of different segments in the programs.
  • Thumbnail Image
    Practical Minimal Perfect Hashing Functions for Large Databases
    Fox, Edward A.; Heath, Lenwood S.; Chen, Qi-Fan; Daoud, Amjad M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1990)
    We describe the first practical algorithms for finding minimal perfect hash functions that have been used to access very large databases (i.e., having over 1 million keys). This method extends earlier work wherein an 0(n-cubed) algorithm was devised, building upon prior work by Sager that described an 0(n-to the fourth) algorithm. Our first linear expected time algorithm makes use of three key insights: applying randomness whereever possible, ordering our search for hash functions based on the degree of the vertices in a graph that represents word dependencies, and viewing hash value assignment in terms of adding circular patterns of related words to a partially filled disk. Our second algorithm builds functions that are slightly more complex, but does not build a word dependency graph and so approaches the theoretical lower bound on function specification size. While ultimately applicable to a wide variety of data and file access needs, these algorithms have already proven useful in aiding our work in improving the performance of CD-ROM systems and our construction of a Large External Network Database (LEND) for semantic networks and hypertext/hypermedia collections. Virginia Disc One includes a demonstration of a minimal perfect hash function running on a PC to access a 130,198 word list on that CD-ROM. Several other microcomputer, minicomputer, and parallel processor versions and applications of our algorithm have also been developed. Tests including those wiht a French word list of 420,878 entries and a library catalog key set with over 3.8 million keys have shown that our methods work with very large databases.