Automatic: Your Smart Driving Assistant Overview
An adapter utilizing a car's OBDII port to collect and display driving data, helping users save money, improve driving behavior, and enable remote car sharing. The device connects to smartphones via a 3G connection, offering features such as crash alerts and instant diagnostics. Automatic's app store allows for customization and third-party app integration, enhancing the overall driving experience.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Persistent Bloom Filter: Membership Testing for the Entire History Yanqing Peng1 Jinwei Guo2 Feifei Li1 Weining Qian2 Aoying Zhou2 1 University of Utah 2 East China Normal University
Membership Testing and Bloom Filter Membership Testing Given a set ? = {?1,?2, } and an element ? Test if x ? Bloom Filter Probabilistic data structure for membership testing Small space Tunable small false positive rate Zero false negative rate 2
Bloom Filter Start with a bitmap of ? bits, initialized to all zero s. Prepare ? hash functions ?:? [0,?) where ? is the domain of ? Insert ?: for all ? = 1, ,?, set the ?(?)-th bit to 1 Membership Testing If exists 1 ? ? that the ?(?)-th bit is 0, return False Otherwise, return True 3
An Example Has IP address 223.12.251.22 ever visited my web server? Log Insert 155.95.78.223 Query 223.12.251.22 BF Insert 87.125.33.64 4
Temporal Case Has IP address 223.12.251.22 ever visited my web server between 9:30am and 9:40am? *Assume time granularity is 1 minute Log Insert Query (9:30am, 155.95.78.223) (9:30am, 223.12.251.22) OR} BF Insert Query (10am, 87.125.33.64) (9:40am, 223.12.251.22) 5
Temporal Membership Testing Temporal Membership Testing Given a temporal set ? = { ??,??, ??,??, }, an element ?, and a time range [?,?] Test if exists ? [?,?] such that ?,? ? Na ve Bloom Filter solution Up to (e-s+1) times of query: slow (? ?+1) where ?0 is the query precision of the BF. Precision: ? = ?0 Looking for A data structure that supports temporal membership testing Still have nice properties in Bloom Filter Compact space Tunable small false positive rate Zero false negative rate 6
Idea: Binary Decomposition Time upper bound = 8, construct a 4-level binary tree Each node has a time range Each node stores the information of corresponding time range Only needs 2 nodes to represent time range [3, 8] Cover Pairwise disjoint Union is exactly the original range Minimal number of nodes 7
PBF-1 Construction A binary tree of Bloom Filters Each node represents a dyadic range [?,?] Each node maintains a BF of elements appears in time [?,?] Elements appeared in [1,4] Elements appeared in [1,2] Elements appeared in [3,4] Root: [1,?] where T is time upper bound ?+? 2 Parent: [?,?] -> left child [?, ], right child Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] ?+? 2 [ ,?], 8
PBF-1 Insertion Insert (?,?): insert element ? to every BF with dyadic range containing timestamp ? Start from root Go either left or right Until reach leaf Elements appeared in [1,4] Insert (x, 2) => Node([1,4]).insert(x); Elements appeared in [1,2] Elements appeared in [3,4] Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] 9
PBF-1 Insertion Insert (?,?): insert element ? to every BF with dyadic range containing timestamp ? Start from root Go either left or right Until reach leaf Elements appeared in [1,4] Insert (x, 2) => Node([1,4]).insert(x); Node([1,2]).insert(x); Elements appeared in [3,4] Elements appeared in [1,2] Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] 10
PBF-1 Insertion Insert (?,?): insert element ? to every BF with dyadic range containing timestamp ? Start from root Go either left or right Until reach leaf Elements appeared in [1,4] Insert (x, 2) => Node([1,4]).insert(x); Node([1,2]).insert(x); Node([2,2]).insert(x); Elements appeared in [1,2] Elements appeared in [3,4] Elements appeared in [1,1] Elements appeared in [3,3] Elements appeared in [4,4] Elements appeared in [2,2] 11
PBF-1 Query Query (?,[?,?]): query element ? to BFs in the cover set of [?,?] until found Start from root If current node is entirely contained in [s,e], query Go left or/and right if intersection is non-empty Elements appeared in [1,4] Until found or finish searching Query (x, [2,4] ) => Elements appeared in [1,2] Elements appeared in [3,4] Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] 12
PBF-1 Query Query (?,[?,?]): query element ? to BFs in the cover set of [?,?] until found Start from root If current node entirely contained in [s,e], query Go left or/and right if intersection is non-empty Elements appeared in [1,4] Until found or finish searching Query (x, [2,4] ) => Node([3,4]).query(x) OR Elements appeared in [1,2] Elements appeared in [3,4] Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] 13
PBF-1 Query Query (?,[?,?]): query element ? to BFs in the cover set of [?,?] until found Start from root If current node entirely contained in [s,e], query Go left or/and right if intersection is non-empty Elements appeared in [1,4] Until found or finish searching Query (x, [2,4] ) => Node([3,4]).query(x) OR Node([2,2]).query(x) Elements appeared in [1,2] Elements appeared in [3,4] Elements appeared in [1,1] Elements appeared in [3,3] Elements appeared in [4,4] Elements appeared in [2,2] 14
Analysis of PBF-1 ?(log(? ?)) BF operations ?(?) Bloom Filters Elements appeared in [1,16] Improvement: Limit minimal granularity at leaves Elements appeared in [1,8] Elements appeared in [9,16] Limit the granularity ? of leaf nodes Use a standard bloom filter for finer queries Elements appeared in [1,4] Elements appeared in [5,8] Elements appeared in [9,12] Elements appeared in [13,16] Example: ? = 4 Standard Bloom Filter (SBF) for finer granularities 15
PBF-1 with limited granularity Limit the granularity ? of leaf nodes Use a standard bloom filter (SBF) as the na ve solution for finer granularities Elements appeared in [1,16] Insert: Insert element ? to every dyadic range containing ?, then insert (?,?) to SBF Elements appeared in [1,8] Elements appeared in [9,16] Example: Insert (x, 6) Node([1,16]).insert(x); Node([1,8]).insert(x); Elements appeared in [1,4] Elements appeared in [5,8] Elements appeared in [9,12] Elements appeared in [13,16] Node([5,8]).insert(x); SBF.insert((x, 6)); SBF 16
PBF-1 with limited granularity Limit the granularity ? of leaf nodes Use a standard bloom filter (SBF) as the na ve solution for finer granularities Elements appeared in [1,16] Query: Query element ? to the (aligned) cover of [?,?] until found. If still not found, issue na ve queries toward SBF Elements appeared in [1,8] Elements appeared in [9,16] Example: Query (x, [4, 13]) Node([5,8]).query(x) OR Elements appeared in [1,4] Elements appeared in [5,8] Elements appeared in [9,12] Elements appeared in [13,16] Node([9,12]).query (x) OR SBF.query((x,4)) OR SBF SBF.query((x,13)); 17
PBF-1 with limited granularity Use ?(?/?) BFs More queries Higher FP rate Elements appeared in [1,16] Can we do better? Elements appeared in [1,8] Elements appeared in [9,16] Sublinear number of BFs? Elements appeared in [1,4] Elements appeared in [5,8] Elements appeared in [9,12] Elements appeared in [13,16] SBF 18
PBF-2 Construction Merge nodes from same level of PBF-1 In PBF-1: insert x into the i-th node of level j In PBF-2: insert (x, i) into the node representing level j Elements appeared in [1,4] [1,4] Attach 0 L0 L0N0 Elements appeared in [1,2] Elements appeared in [3,4] [1,2] Attach 0 [3,4] Attach 1 L1N1 L1N0 L1 Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] [1,1] Attach 0 [2,2] Attach 1 [3,3] Attach 2 [4,4] Attach 3 L2 L2N2 L2N0 L2N1 L2N3 19
PBF-2 Insertion Elements appeared in [1,4] [1,4] Attach 0 L0N0 L0 Elements appeared in [1,2] Elements appeared in [3,4] L1N1 [1,2] Attach 0 [3,4] Attach 1 L1N0 L1 Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] [1,1] Attach 0 [2,2] Attach 1 [3,3] Attach 2 [4,4] Attach 3 L2 L2N2 L2N0 L2N1 L2N3 Insert (x, 2) => Node(L0).insert((x, 0)); Node(L1).insert((x, 0)); Node(L2).insert((x, 1)); Insert (x, 2) => Node(L0N0).insert(x); Node(L1N0).insert(x); Node(L2N1).insert(x); Use LiNj to represent the j-th node at level i Use Li to represent the i-th node representing level i 20
PBF-2 Query [1,4] Attach 0 L0 Elements appeared in [1,4] L0N0 [1,2] Attach 0 [3,4] Attach 1 L1 Elements appeared in [1,2] Elements appeared in [3,4] L1N1 L1N0 [1,1] Attach 0 [2,2] Attach 1 [3,3] Attach 2 [4,4] Attach 3 L2 Elements appeared in [1,1] Elements appeared in [2,2] Elements appeared in [3,3] Elements appeared in [4,4] L2N2 L2N0 L2N1 L2N3 Query (x, [2,4] ) => Node(L1N1).query(x) OR Node(L2N1).query(x) Query (x, [2,4] ) => Node(L1).query((x, 1)) OR Node(L2).insert((x, 1)) 21
Analysis of PBF-2 ?(log(? ?)) times of insertion ?(log?) Bloom Filters Elements appeared in [1,16] Why not use even less BFs? Elements appeared in [1,8] Elements appeared in [9,16] Elements appeared in [1,4] Elements appeared in [5,8] Elements appeared in [9,12] Elements appeared in [13,16] 22
Bit Allocation Given a space budget of ? bits, and a construct of PBF, how to allocate bits to BFs? Intuition: more elements, more popular => more bits Extreme examples No elements inserted in a dyadic range => 0 bit No query will access to a dyadic range => 0 bit Optimal off-line allocation scheme Write FP rate as a FP(#M, #D, #F) #M = ?1,?2, represents #bits allocated to each BF #? = ?1,?2, represents #elements in each BF #? = ?1,?2, represents #query accesses to each BF Assume we know #D and #F, calculate argmin #? ?? subject to #? = ? 23
Bit Allocation ??:Number of elements in the :Number of elements in the i i- -th th BF ??:Number of accesses to the :Number of accesses to the i i- -th th BF ??:Number of bits allocated for the :Number of bits allocated for the i i- -th th BF ??:A parameter needs to be solved :A parameter needs to be solved ? : Total number of bits (budget) : Total number of bits (budget) BF BF BF 24
Bit Allocation Split time into epochs Learn the parameters based on previous epochs Many learning tools can apply 25
Experiment Setup Dataset EDGAR Log: 2, 127, 749 distinct log entries from 25, 497 different clients Network trace: 2, 199, 573 distinct log entries from 124, 427 different clients Parameters About 50x space saving 26
Experimental Results Slightly higher insertion cost Magnitudes lower query cost 27
Experimental Results PBF1-online < PBF2-online ~ PBF2-offline < PBF1-offline 28
Experimental Results Low impact on query length PBF1-online < PBF2-online ~ PBF2-offline < PBF1-offline 29
Comparison between PBF-1 & PBF-2 PBF-1 Linear number of BFs, hard to setup and maintain Optimal solution in offline setting, hard to learn parameters in online setting PBF-2 Logarithmic number of BFs, easy to setup and maintain Slightly worse performance in offline setting, good online performance Back to the question: Why not use less BFs? Tradeoff Between #BF and Optimization Potential PBF-Single: One BF, no bit allocation, no major difference from na ve PBF 30 Persistent Bloom Filter
Thank you! Source code: https://bitbucket.org/gjwei1987/pbf 31
Backup Slides 32 Persistent Bloom Filter
Persistent Count-Min Sketch Persistent Count-Min Sketch [Wei 14] Given a temporal Set ? = ??,??, ??,??, , an element ?, and a time range ?,? Return how many times ? appeared in ? within ?,? |{? [?,?]| ?,? ?}| Compare to temporal membership testing Given a temporal Set ? = ??,??, ??,??, , an element ?, and a time range ?,? Return if ? appeared ? within ?,? ? ?,? ?,? ? =?0 33
Persistent Count-Min Sketch Persistent Count-Min Sketch [Wei 14] Given a temporal Set ? = ??,??, ??,??, , an element ?, and a time range ?,? Return how many times ? appeared in ? within ?,? |{? [?,?]| ?,? ?}| Compare to temporal membership testing Given a temporal Set ? = ??,??, ??,??, , an element ?, and a time range ?,? Return if ? appeared ? within ?,? ? ?,? ?,? ? =?0 Additive error of CM-sketch When truth=0, with high probability result=? > 0 34
