Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

First pass of memo-based indexing #7

Open
dnorman opened this issue Mar 3, 2017 · 1 comment
Open

First pass of memo-based indexing #7

dnorman opened this issue Mar 3, 2017 · 1 comment
Assignees
Milestone

Comments

@dnorman
Copy link
Collaborator

dnorman commented Mar 3, 2017

Deliverables:

  • Initial implementation of commutative memo merging
  • Complete implementation unbase::index::FixedIndex class
  • Update slab / context to use this in lieu of HashMap
  • Self-host index subject lookup if possible ( not clear if this is actually possible )
@dnorman dnorman self-assigned this Mar 3, 2017
@dnorman dnorman added this to the Core Functionality milestone Mar 3, 2017
@dnorman
Copy link
Collaborator Author

dnorman commented Mar 5, 2017

FixedIndex now minimally works, as does basic query context MemoRefHead merging.
The latter allows the relationship traversal to consider memos which are in the query context, but which have not yet generated parent node edits.

What we have is essentially this:

IE: the creation of the basic tree structure, and then edits to the index leaves to reflect the "record" being indexed.

Subsequent passes will enable context to periodically consolidate itself by emitting edits to the non-leaf index subjects, and pruning the context MemoRefHead to include only the edits generated. These will reference the prior leaf subject edits directly, allowing for those Memorefs to be removed from the context, while still yielding the same result.

Proposed next items:

  • Manual context compression, triggered in the test suite for now, but later to be triggered automatically as the context expands in the natural course of editing.
  • Update FixedIndex to handle data types other than int
  • Update FixedIndex to not act badly when values > 256^5 are indexed
  • Generation of Keyframe memos by the context ( AKA Materialized Memos )
  • Commutative merging for some memo types ( specifically the index )

Please note that FixedIndex is intended to be temporary. I think balanced trees or similar should be possible, but it's not critical for the Alpha necessarily.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant