A Dictionary of
`
`Computing
`
`SIXTH EDITION
`
`OXFORD
`
`UNIVERSITY PRESS
`
`QUALCOMM EXHIBIT 2011
`Intel v. Qualcomm
`IPR2018-01334
`
`

`

`OXFORD
`
`UNIVERSITY PRESS
`Great Clarendon Street, Oxford OX2 6DP
`Oxford University Press is a department of the University of Oxford.
`It furthers the University's objective of excellence in research, scholarship,
`and education by publishing worldwide in
`Oxford New York
`Auckland Cape Town Dar es Salaam Hong Kong Karachi
`Kuala Lumpur Madrid Melbourne Mexico City Nairobi
`New Delhi Shanghai Taipei Toronto
`With offices in
`Argentina Austria Brazil Chile Czech Republic France Greece
`Guatemala Hungary Italy Japan Poland Portugal Singapore
`South Korea Switzerland Thailand Turkey Ukraine Vietnam
`Oxford is a registered trade mark of Oxford University Press
`in the UK and in certain other countries
`Published in the United States
`by Oxford University Press Inc., New York
`
`© Market House Books Ltd, 1983, 1986, 1990, 2004, 2008
`
`The moral rights of the author have been asserted
`Database right Oxford University Press (maker)
`
`First edition 1983
`Second edition 1986
`Third edition 1990
`Fourth edition 1996
`Fifth edition 2004
`Sixth edition 2008
`
`All rights reserved. No part of this publication may be reproduced,
`stored in a retrieval system, or transmitted in any form or by any means,
`without the prior permission in writing of Oxford University Press,
`or as expressly permitted by law, or under terms agreed with the appropriate
`reprographics rights organization. Enquiries concerning reproduction
`outside the scope of the above should be sent to the Rights Department,
`Oxford University Press, at the address above
`
`You must not circulate this book in any other binding or cover
`and you must impose this same condition on any acquirer
`
`British Library Cataloguing in Publication Data
`Data available
`
`Library of Congress Cataloging in Publication Data
`Data available
`
`Typeset by Market House Books Ltd.
`Printed in Great Britain
`on acid-free paper by
`Clays Ltd, St Ives pie
`ISBN 978-0-19-923401-l
`
`10 9 8 7 6 5 4 3 2 1
`
`QUALCOMM EXHIBIT 2011
`Intel v. Qualcomm
`IPR2018-01334
`
`

`

`BSP tree
`
`58
`
`fully charged bucket, or full bucket, is equiv(cid:173)
`alent to a logic l; an uncharged or empty
`bucket is equivalent to a logic 0. The charge
`may be passed through an array of capaci(cid:173)
`tors and associated electronics, which to(cid:173)
`gether form a bucket brigade.
`bucket sort An external sort in which the
`records to be sorted are grouped in some
`way, and each group stored in a distinct
`*bucket. Different buckets will probably be
`stored on different storage devices. If search(cid:173)
`ing is to be performed on the data, then each
`bucket should contain records with the same
`hash value (see HASHING). In this way all the
`records that might contain therequired key
`rriay be fetched from the external memory at
`once.
`buddy system A method of implement(cid:173)
`ing a *memory management system. The
`available memory is partitioned into blocks
`whose sizes are always exact powers of two.
`A request for m bytes of memory is satisfied
`by allocating a block of size 2!>+ 1 where
`2" < m $. 2!>+ 1
`If no block of this size is available then a
`larger block is subdivided, more than once if
`necessary, until a block of the required size is
`generated. When memory is freed it is com(cid:173)
`bined with a free adjacent block (if one ex(cid:173)
`ists) to produce a larger block, always
`preserving the condition that block sizes are
`exact powers of two.
`buffer 1. A temporary memory for data,
`normally used to accommodate the differ(cid:173)
`ence in the rate at which two devices can
`handle data during a transfer. The buffer
`may be built into a peripheral device, such
`as a printer or disk drive, or may be part of
`the system's main memory. See BUFFERING.
`2. A means of maintaining a short but vary(cid:173)
`ing length of magnetic tape between the
`reels and the •capstan and head area of a
`tape transport, in order that the acceleration
`of the tape at the reels need not be as great
`as that of the tape at the capstan. Streaming
`tape transports and many types of cartridge
`drives do not use buffers and are therefore
`limited to lower accelerations of the tape in
`the area of the head and (if there is one) cap(cid:173)
`stan. 3. Any circuit or device that is put be(cid:173)
`tween two others to smooth changes in rate
`or level or allow asynchronous operation.
`For example, line *drivers can be used to iso(cid:173)
`late (or buffer) two sets of data lines.
`
`*Bezier patch is defined by *Bezier curves.
`Given a characteristic polygon defined by
`vertices r;j, i = 0,1, ... p, j = 0,1, .. . q, the B(cid:173)
`spline patch is defined by
`p q
`r(u,v) =~
`
`
`rijBp,;+ 1 Cu)Bp,j+ t(v)
`
`1~
`
`where Bis the B-spline basis function of de(cid:173)
`gree p.
`BSP tree Shortforbinaiy space-partition(cid:173)
`ing tree.
`B+ tree See B-TREE.
`B-tree (orb-tree) 1. (balanced multiway
`search tree) of *degree n (;:>:2). A •multiway
`search tree of degree n in which the root
`node has degree ;:>:2, every nonterminal node
`other than the root has degree k, where
`n/2 $.k$. n
`and every leaf node occurs at the same
`level. Originally defined by R. Beyer and
`E. McCreight, the data structure provides
`an efficient dynamic retrieval device.
`An extension to a B-tree is a B+ tree, which
`is used as a primary index to an *indexed file .
`It comprises two parts: a sequential index
`containing an entry for every record in the
`file, and a B-tree acting as a multilevel index
`to the sequential index entries. B+ trees are
`used in *VSAM. 2. A binary tree with no
`nodes of degree one.
`BTron SeeTRON.
`bubble jet A type of *inkjet printer.
`bubble memory See MAGNETIC BUBBLE
`MEMORY.
`bubble sort (exchange selection) A form
`of •sorting by exchanging that simply inter(cid:173)
`changes pairs of elements that are out of
`order in a sequence of passes through the
`file, until no such pairs exist. The method is
`not competitive with •straight insertion.
`bucket 1. A subdivision of a *data file, serv(cid:173)
`ing as the unit within which records are lo (cid:173)
`cated. Buckets are specially used in
`connection with *hashing techniques, and
`with indexing techniques (see INDEX) where
`index entries point to groups of records. In
`these circumstances, hashing or indexing
`will yield the address of the start of the
`bucket; the location for storage or retrieval
`within the bucket will then be found by
`searching. 2. A capacitor whose electric
`charge is used as a form of dynamic *RAM. A
`
`-
`
`QUALCOMM EXHIBIT 2011
`Intel v. Qualcomm
`IPR2018-01334
`
`