algorithm - Non-trivial usage of count-min sketch data-structure -


i have large array increasing values - this:

array = [0, 1, 6, 6, 12, 13, 22, ..., 92939, 92940]

and want use interpolation-search algorithm on it. size of array variable, new elements added end of array.

i need find index of element, let's call x.

y = find(x in array)

y must index of element array such array[y] >= x find can implemented binary search complicated reasons want implemented using interpolation search. interpolation search tries guess correct position of x looking @ bounds of array. if first array value 0 , last 100 , want find position of value 25 than, if array length 1000, need @ value @ index 250 first. works charm if values of array evenly distributed. if not evenly distributed, interpolation search can work slower binary search (there optimizations possible).

i'm trying speed search in such cases using count-min sketch data structure. when appending new element array add data count-min sketch data-structure.

z = 1005000  elements_before_z = len(array) array.append(z) count_min_sketch.add(z, elements_before_z)   # z key , elenents_before_z - count

using approach can guess position of searched element x approximately. can result in search speedup if guess correct, i've ran problems.

  1. i don't know if x in array , count_min_sketch have seen value. if case can correct value out of count_min_sketch datastructure. if it's not - 0 or other value (worst case scenario).

  2. collisions. if value x have been seen count_min_sketch object - correct value or larger value. if count min sketch used counting word occurrence in document - not problem because collisions rare , error less or equal number of collisions (it used this: count_min_sketch.add(z, 1)). in case, every collision can result in large error, because add large numbers every key.

is possible use count-min sketch in such way (adding large number of entries every time)?


Comments

Post a Comment

Popular posts from this blog

commonjs - How to write a typescript definition file for a node module that exports a function? -

consider, toml node module can use: // toml.d.ts declare module toml { export function parse(value:string):any; } declare module "toml" { export = toml; } then: /// <reference path="../../../../../defs/toml/toml.d.ts"/> import toml = require('toml'); toml.parse(...); however, node module export single function, such 'glob' ( https://github.com/isaacs/node-glob ). the node usage of module be: var glob = require("glob") glob("*.js", {}, callback(err, files) { ... }); you'd naively expect this: // glob.d.ts declare function globs(paths:string, options:any, callback:{(err:any, files:string[]):void; ...but because typescripts 'import' semantics bit strange, seems can use 'import .. = require()' statement alias modules . trying call: /// <reference path="../../../../../defs/glob/glob.d.ts"/> import blog = require('glob'); results in: error ts2072: mod
Read more

openid - Okta: Failed to get authorization code through API call -

i'm integrating okta own idp server using okta's api. i'm implementing authorization code flow following steps below: in own server, use /api/v1/authn endpoint sessiontoken. use sessiontoken obtain authorization calling endpoint: /oauth2/v1/authorize?client_id=" + clientid + "&sessiontoken=" + sessiontoken + "&response_type=code&response_mode=query&scope=openid&redirect_uri=" + redirecturl + "&state=evanyang&nonce=" it's supposed return response status code 302 , location header containing redirect url code value. however, keep getting response status code 200 , without location header, html body saying "you using unsupported browser." , "javascript disabled on browser." according api documentation: http://developer.okta.com/docs/api/resources/oidc.html#authentication-request , sessiontoken parameter sufficient this: an okta one-time sessiontoken. allows api-based
Read more

thorough guide for profiling racket code -

did googling ("racket profiling", "racket measure performance"), didn't find , there no examples in docs. did google "profile" search on htdp - no luck. (profile (f ...)) output isn't obvious other small snippets. ideally want python's python -m cprofile usage examples. when search "python profiling", both duckduckgo , google give top result: 26.4. python profilers . (although scanned quickly, seems more of reference "thorough usage guide" examples. if had else in mind, perhaps please link that?) the equivalent racket documentation be: profile: statistical profiler . a usage example: #lang racket (require profile) (profile-thunk (thunk (function-to-profile arg0 arg1) )) here (thunk e) convenience (lambda () e) . bigger example: #lang racket (module mod racket (provide f) (define (f) (for/list ([i 10000]) i))) (require (prefix-in mod: 'mod)) (define (f) (for ([i 10000
Read more