Theory and Practice of Time-Space Trade-Offs in Memory Limited Search

Local TagsStatisticsRevisionsRelease HistoryDetails

Theory and Practice of Time-Space Trade-Offs in Memory Limited Search

Edelkamp, S., & Meyer, U. (2001). Theory and Practice of Time-Space Trade-Offs in Memory Limited Search. In F. Baader, G. Brewka, & T. Eiter (Eds.), Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01) (pp. 169-184). Berlin, Germany: Springer.

Item is Released

show all hide all

Basic

show hide

Bookmark this item: http://pubman.mpdl.mpg.de/pubman/item/escidoc:1330596:2

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Edelkamp, Stefan, Author
Meyer, Ulrich¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, escidoc:24019

Content

show

hide

Free keywords: -

Abstract: We establish $O(n \log n)$ minimum-space algorithms that omit both the open and the closed list to determine the shortest path between every two nodes and study the gap in between full memorization in a hash table and the information-theoretic lower bound. The proposed structure of suffix-lists elaborates on a concise binary representation of states by applying bit-state hashing techniques. Significantly more states can be stored while searching and inserting $n$ items into suffix lists is still available in $O(n \log n)$ time. Bit-state hashing leads to the new paradigm of partial iterative-deepening heuristic search, in which full exploration is sacrificed for a better detection of duplicates in large search depth. We give first promising results in the application area of communication protocols.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02 Published in Print: 2001

Pages: -

Publishing info: -

Table of Contents: -

Rev. Method: -

Identifiers: eDoc: 518172
Other: Local-ID: C1256428004B93B8-61CD1C052EFB5BBEC1256A6900496CFE-EdelkampMeyer2001

Degree: -

Event

show

hide

Title: Untitled Event

Place of Event: Wien, Österreich

Start-/End Date: -

Legal Case

show

Source 1

show

hide

Title: Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01)

Source Genre: Proceedings

Creator(s):
Baader, F.¹, Editor
Brewka, G., Editor
Eiter, T., Editor

Affiliations:
1 Programming Logics, MPI for Informatics, Max Planck Society, escidoc:40045

Publ. Info: Berlin, Germany : Springer

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 169 - 184 Identifier: ISBN: 3-540-42612-4

Source 2

show

hide

Title: Lecture Notes in Computer Science

Source Genre: Series

Creator(s):
-

Affiliations:
-

Publ. Info: -

Pages: - Volume / Issue: 2174 Sequence Number: - Start / End Page: - Identifier: -