{"id":3799871,"name":"github.com/openacid/polyarray","ecosystem":"go","description":"package polyarray uses polynomial to compress and store an array of uint32.\nA uint32 costs only 5 bits in a sorted array of a million number in range [0,\n1000*1000].\n\nWe use a polynomial y = a + bx + cx² to describe the overall trend of the\nnumbers.\nAnd for every number i we add a residual to fit the gap between y(i) and\nnums[i].\nE.g. If there are 4 numbers: 0, 15, 33, 50\nThe polynomial and residuals are:\n\nIn this case the residuals require 3 bits for each of them.\nTo retrieve the numbers, we evaluate y(i) and add the residual to it:\n\nAnother space efficient data structure to store uint32 array is trie or prefix\ntree or radix tree. It is possible to use bitmap-based btree like structure\nto reduce space(very likely in such case it provides higher compression rate).\nBut it requires the array to be sorted.\n\nPolyArray does not have such restriction. It is more adaptive with data\nlayout. To achieve high compression rate, it only requires the data has a\noverall trend, e.g., roughly sorted, as seen in the above 4 integers\nexamples. Additionally, it also accept duplicated element in the array, which\na bitmap based or tree-like data structure does not allow.\n\nPolyArray splits the entire array into segments(Seg),\neach of which has 1024 numbers.\nAnd then it splits every segment into several spans.\nEvery span has its own polynomial. A span has 16*k numbers.\nA segment has at most 64 spans.\n\nA PolyArray is a compacted data structure.\nThe original data structures are defined as follow(assumes original user data\nis `nums []uint32`):\n\nA span stores 16*k int32 in it, where k ∈ [1, 64).\n\n`Seg.SpansBitmap` describes the layout of Span-s in a Seg.\nA \"1\" at i-th bit and a \"1\" at j-th bit means a Span stores\n`nums[i*16:j*16]`, e.g.:\n\nIn the above example:\n\n`Seg.OnesCount` caches the total count of \"1\" in all preceding Seg.SpansBitmap.\nThis accelerate locating a Span in the packed field PolyArray.Polynomials .\n\n`Span.width` is the count of numbers stored in this span.\nIt does not need to be stored because it can be calculated by counting the\n\"0\" between two \"1\" in `Seg.SpansBitmap`.\n\n`Span.Polynomial` stores 3 coefficients of the polynomial describing the\noverall trend of this span. I.e. the `[a, b, c]` in `y = a + bx + cx²`\n\n`Span.Config.Offset` adjust the offset to locate a residual.\nIn a span we want to have that:\n\nBut if the preceding span has smaller residual width, the \"offset\" could be\nnegative, e.g.: span[0] has residual of width 0 and 16 residuals,\nspan[1] has residual of width 4.\nThen the \"offset\" of span[1] is `-16*4` in order to satisify:\n`(-16*4) + i * 4` is the correct residual position, for i in [16, 32).\n\n`Span.Config.ResidualWidth` specifies the number of bits to\nstore every residual in this span, it must be a power of 2: `2^k`.\n\n`Span.Residuals` is an array of residuals of length `Span.width`.\nEvery elt in it is a `ResidualWidth`-bits integers.\n\nPolyArray compact `Seg` into a dense format:\n\n`PolyArray.Residuals` simply packs the residuals of every nums[i] together.","homepage":"https://github.com/openacid/polyarray","licenses":"Apache-2.0","normalized_licenses":["Apache-2.0"],"repository_url":"https://github.com/openacid/polyarray","keywords_array":[],"namespace":"github.com/openacid","versions_count":4,"first_release_published_at":"2020-11-09T11:26:03.000Z","latest_release_published_at":"2020-11-23T09:41:29.000Z","latest_release_number":"v0.1.3","last_synced_at":"2026-03-19T10:05:46.365Z","created_at":"2022-04-11T18:20:42.428Z","updated_at":"2026-03-19T10:05:46.365Z","registry_url":"https://pkg.go.dev/github.com/openacid/polyarray","install_command":"go get github.com/openacid/polyarray","documentation_url":"https://pkg.go.dev/github.com/openacid/polyarray#section-documentation","metadata":{},"repo_metadata":{},"repo_metadata_updated_at":"2023-03-21T19:06:33.850Z","dependent_packages_count":0,"downloads":null,"downloads_period":null,"dependent_repos_count":0,"rankings":{"downloads":null,"dependent_repos_count":9.345852080216646,"dependent_packages_count":6.999148183520997,"stargazers_count":null,"forks_count":null,"average":8.172500131868823},"purl":"pkg:golang/github.com/openacid/polyarray","advisories":[],"docker_usage_url":"https://docker.ecosyste.ms/usage/go/github.com/openacid/polyarray","docker_dependents_count":null,"docker_downloads_count":null,"usage_url":"https://repos.ecosyste.ms/usage/go/github.com/openacid/polyarray","dependent_repositories_url":"https://repos.ecosyste.ms/api/v1/usage/go/github.com/openacid/polyarray/dependencies","status":null,"funding_links":[],"critical":null,"issue_metadata":null,"versions_url":"https://packages.ecosyste.ms/api/v1/registries/proxy.golang.org/packages/github.com%2Fopenacid%2Fpolyarray/versions","version_numbers_url":"https://packages.ecosyste.ms/api/v1/registries/proxy.golang.org/packages/github.com%2Fopenacid%2Fpolyarray/version_numbers","dependent_packages_url":"https://packages.ecosyste.ms/api/v1/registries/proxy.golang.org/packages/github.com%2Fopenacid%2Fpolyarray/dependent_packages","related_packages_url":"https://packages.ecosyste.ms/api/v1/registries/proxy.golang.org/packages/github.com%2Fopenacid%2Fpolyarray/related_packages","codemeta_url":"https://packages.ecosyste.ms/api/v1/registries/proxy.golang.org/packages/github.com%2Fopenacid%2Fpolyarray/codemeta","maintainers":[]}